package com.hxm.demo.newcoder;

public class TestBM2 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode listNode = reverseBetween2(head, 2, 4);
        System.out.println(listNode);
    }

    public static ListNode reverseBetween1(ListNode head, int m, int n) {
        // write code here
        if (head == null || head.next == null || m == n) {
            return head;
        }
        int i = 0;
        ListNode pre = new ListNode(head.val);
        ListNode newListNode = pre;
        ListNode between = null;
        ListNode tail = null;
        while (head != null) {
            ListNode temp1 = head.next;
            if (m >= 2 && i < m - 2) {
                pre.next = new ListNode(temp1.val);
                pre = pre.next;
            }
            if (i >= m - 1 && i < n) {
                head.next = between;
                between = head;
                if (i == m - 1) {
                    tail = between;
                }
            }
            if (i >= n) {
                tail.next = new ListNode(head.val);
                tail = tail.next;
            }
            head = temp1;
            i++;
        }
        if (m == 1) {
            return between;
        }
        pre.next = between;
        return newListNode;
    }

    public static ListNode reverseBetween2(ListNode head, int m, int n) {
        // write code here
        ListNode vartual = new ListNode(-1);
        vartual.next = head;

        ListNode pre = vartual;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }

        ListNode right = pre.next;
        for (int i = 0; i < n - m; i++) {
            right = right.next;
        }

        ListNode left = pre.next;
        ListNode tail = right.next;

        pre.next = null;
        right.next = null;

        ListNode mid = null;
        ListNode cur = left;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = mid;
            mid = cur;
            cur = temp;
        }

        pre.next = mid;
        left.next = tail;
        return vartual.next;
    }
}
